package syf.rank;

import java.util.Arrays;

public class ShellRank {
    public static void main(String[] args) {
        int max=80000;
//        int[] arr={8,9,1,7,2,3,5,4,6,0};;//new int[5];
        int[] arr=new int[max];
        for (int i=0;i<max;i++){
            arr[i]=(int)(Math.random()*100000);
        }
        long now=System.currentTimeMillis();
//        arr=shell(arr);
        arr=shellImp(arr);
        long end=System.currentTimeMillis();
        System.out.println(end-now);
    }
    /**
     * 希尔排序--交换
     * @param arr 传入的待排序数组
     * @return 排序完成后数组
     */
    public static int[] shell(int[]arr){
        int tmp;
        //要进行的轮数
        for (int gap=arr.length/2;gap>0;gap/=2){
            //数据遍历次数 gap为分的组数 分成一组需比较 arr.length-1 两组则为 arr.length-2 n组则为arr.length-n
            for (int i=gap;i<arr.length;i++){
                //遍历所有数据,每个组单独进行， 从后往前
                for (int j=i-gap;j>=0;j-=gap){
                    //前面的大于后面的则交换
                    if (arr[j]>arr[j+gap]){
                        tmp=arr[j+gap];
                        arr[j+gap]=arr[j];
                        arr[j]=tmp;
                    }
                }
            }System.out.println(Arrays.toString(arr));
        }
        return arr;
//        int tmp;
//        int num=arr.length/2;
//        //跑length/2次
//        for (int i=num;i<arr.length;i++){
//            //分成的组赋值
//            for (int j=i-num;j>=0;j-=num){
//                if (arr[j]>arr[j+num]){
//                    tmp=arr[j+num];
//                    arr[j+num]=arr[j];
//                    arr[j]=tmp;
//                }
//            }
//        }
//        num=num/2;
//        System.out.println(Arrays.toString(arr));
//        //跑length/2/2次
//        for (int i=num;i<arr.length;i++){
//            //分成的组赋值
//            for (int j=i-num;j>=0;j-=num){
//                if (arr[j]>arr[j+num]){
//                    tmp=arr[j+num];
//                    arr[j+num]=arr[j];
//                    arr[j]=tmp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
//        num=(num<=2)?1:num/2/2;
//        //跑length/2/2次
//        for (int i=num;i<arr.length;i++){
//            //分成的组赋值
//            for (int j=i-num;j>=0;j-=num){
//                if (arr[j]>arr[j+num]){
//                    tmp=arr[j+num];
//                    arr[j+num]=arr[j];
//                    arr[j]=tmp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
//        return arr;
    }

    /**
     * 移位式的
     * @param arr
     * @return
     */
    //移位式的
    public static int[] shellImp(int[]arr){
        int tmp;
        int index;
        //要进行的轮数
        for (int gap=arr.length/2;gap>0;gap/=2){
            //数据遍历次数 gap为分的组数 分成一组需比较 arr.length-1 两组则为 arr.length-2 n组则为arr.length-n
            for (int i=gap;i<arr.length;i++){
                //后一个间隔的值，即无序数组中的值
                index=i;//下标
                tmp=arr[index];//值
                //前一个值的下标必须大于等于0 且 要插入的值小于前面的值时进行覆盖
                while (index-gap>=0&&tmp<arr[index-gap]){
                    //前面那个数的值覆盖要插入的值，要插入数的值保存在tmp中
                    arr[index]=arr[index-gap];
                    //下标减去间隔，向前移动 减去后的值为当前有序数组中被替换掉位置的数的下标
                    index-=gap;
                }
                arr[index]=tmp;
            }
//            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }
}
